package main.leetcode.offer.firstround.from51to68;

import java.util.Arrays;

/**
 * 60.n个骰子的点数
 *
 * <p>把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
 *
 * <p>
 *
 * <p>你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
 *
 * <p>
 *
 * <p>示例 1: 输入: 1 输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
 *
 * <p>示例 2: 输入: 2 输出:
 * [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]
 *
 * <p>限制：1 <= n <= 11
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex60 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(new ex60().twoSum(3)));
    }

    public double[] twoSum(int n) {
        int[][] dp = new int[n][6 * n]; // dp[i][j]表示i+1个骰子点数和为j+1的次数
        // 初始化，一个骰子，六个数每个数可能出现的次数都为1
        for (int i = 0; i < 6; ++i) dp[0][i] = 1;
        for (int i = 1; i < n; ++i) {
            for (int j = i; j < (i + 1) * 6; ++j) {
                // 动态转移：F(n,s)=F(n−1,s−1)+F(n−1,s−2)+F(n−1,s−3)+F(n−1,s−4)+F(n−1,s−5)+F(n−1,s−6)
                for (int k = 1; k < 7; ++k) {
                    if (k > j) break;
                    dp[i][j] += dp[i - 1][j - k];
                }
            }
        }
        double[] res = new double[5 * n + 1];
        double sum = Math.pow(6, n);
        for (int i = 0, j = n - 1; i < res.length; ++i, ++j) {
            res[i] = dp[n - 1][j] / sum;
        }
        System.out.println(Arrays.deepToString(dp));
        return res;
    }
}
